package leetcode.pre50;


/**
 * 给定两个整数，被除数 dividend 和除数 divisor。
 * <p>
 * 将两数相除，要求不使用乘法、除法和 mod 运算符。
 * <p>
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 * <p>
 * 整数除法的结果应当截去（truncate）其小数部分，
 * <p>
 * 例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: dividend = 10, divisor = 3
 * 输出: 3
 * 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
 * 示例 2:
 * <p>
 * 输入: dividend = 7, divisor = -3
 * 输出: -2
 * 解释: 7/-3 = truncate(-2.33333..) = -2
 *  
 * <p>
 * 提示：
 * <p>
 * 被除数和除数均为 32 位有符号整数。
 * <p>
 * 除数不为 0。
 * <p>
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。
 * <p>
 * 本题中，如果除法结果溢出，则返回 231 − 1。
 * <p>
 * <p>
 * TODO  除法法则：   a / b = c .... d
 * TODO   ab异号，则c为负，  ab同号，则c为正  【乘法逆运算】
 * TODO   余数d的符号同被除数 a
 *
 * @date 2020/6/1 16:17
 */
public class Code29_Divide_两数相除 {

    public static void main(String[] args) {
//        System.out.println(-3 / 2 + " " + -3 % 2);
//        System.out.println(-3 / -2 + " " + -3 % -2);
//        System.out.println(3 / -2 + " " + 3 % -2);
//        System.out.println(divide(10, 3));
//        System.out.println(divide(7, -3));
//        System.out.println(divide(Integer.MIN_VALUE, -1));
        System.out.println(divide3(10, 3));
//        System.out.println(Integer.MAX_VALUE + 1);
//        System.out.println(0-Integer.MIN_VALUE);
//

    }


    /**
     * 方法1：利用除法本质思想，a中有多少个b，处理边界。 时间复杂度很大
     * a和b都是整数
     * TODO  1、边界问题：MAX_VALUE / - 1 出界
     * TODO  2、注意：0 - MIN_VALUE = MIN_VALUE，被除数和除数都要考虑
     *       TODO 处理方法，1)MIN_VALUE+1处理再换转换，最后再次处理
     *       TODO 2)使用long接受INT_MIN_VALUE,这样 0 - INT_MIN_VALUE不会越界了
     *
     * @param a
     * @param b
     * @return
     */
    public static int divide(int a, int b) {
        //
        if (b == 0) return 0;
        if (b == 1) return a;
        if (b == -1)
            return
                    a == Integer.MIN_VALUE
                            ? Integer.MAX_VALUE  //溢出
                            : -a;

        //使用long接受，否则若a或b为INT_MIN，0 - INT_MIN 还是INT_MIN出错
        //把a和b转为正整数,标记商的符号
        long m = a;
        long n = b;
        boolean positive = true;
        if (m < 0 && n > 0 || m > 0 && n < 0)
            positive = false;
        m = Math.abs(m);
        n = Math.abs(n);
        int res = 0;
        //TODO 这里很费时间
        while (m >= n) {
            m -= n;
            res++;
        }
        return positive ? res : -res;
    }

    /**
     * 方式2：思路同方式1：但是为了避免0-INT_MIN = INT_MIN,
     * 可以将a和b都置为负数
     */
    public static int divide2(int a, int b) {
        if (b == 0) return 0;
        if (b == 1) return a;
        if (b == -1)
            return
                    a == Integer.MIN_VALUE
                            ? Integer.MAX_VALUE  //溢出
                            : -a;

        //a和b是否同号，如果不是，把a和b转为负数
        //如果把负数转为正数，-INT_MIN = INT_MIN，转为MAX溢出
        //但是把INT_MAX转为 负数就不会溢出
        boolean flag = true;
        if (a < 0 && b > 0) {
            b = -b;
            flag = false;
        } else if (a > 0 && b < 0) {
            a = -a;
            flag = false;
        } else if (a > 0 && b > 0) {
            a = -a;
            b = -b;
        }
        int res = 0;
        //a比b小的多， a - b就是分出一个b
        //TODO 这里很费时间
        while (a <= b) {
            a -= b;  //a + Math.abs(b) -> 0向0靠近
            res++;
        }
        return flag ? res : -res;

    }

    /**
     * 方式3：在上面浪费时间那里进行加速。
     * 举个例子13 / 3
     * 13 - 3 > 3 , res >= 1
     * 13 - 2* 3 >3 , res >=2
     * 13 - 2*2* 3 >3 , res >=2*2
     * 13 - 2*2*2* 3 < 3 , 所以说res 在4和8之间，
     * 令 diff = 13 - 2*2*2*3,然差里再递归上述方法
     */
    public static int divide3(int a, int b) {
        if (b == 0) return 0;
        if (b == 1) return a;
        if (b == -1)
            return a == Integer.MIN_VALUE
                    ? Integer.MAX_VALUE :
                    -a;
        //可以使用long避免 a = INT_MIN  0- a = a的问题
        boolean positive = true;
        long m = a;
        long n = b;
        if (m < 0 && n > 0 || m > 0 && n < 0)
            positive = false;
        m = Math.abs(m);
        n = Math.abs(n);
        int res = (int) doDiv2(m, n);
        return positive ? res : -res;
    }

    /**
     * 两个正整数相除递归版 m / n
     *
     * @param m
     * @param n
     * @return
     */
    private static long doDiv(long m, long n) {
        //base case
        if (m < n) return 0;
        //base case
        if (m < (n << 1)) return 1;
        //m至少是 n的两倍
        long res = 0;
        long tempN = n;
        long count = 1;
        while (m >= (tempN << 1)) {
            //count翻倍，累加到res
            res += (count <<= 1);
            //tempN也翻倍
            tempN <<= 1;
            //更新剩下的差值
            m -= tempN;
        }
        // m <  tempN<<1
        return res + doDiv(m, n);
    }
    /**
     * m / n
     * 迭代版
     */

    private static long doDiv2(long m, long n) {
        long res = 0;
        while (true){
            if(m < n) return res;
            if(m < 2*n) return res + 1;
            long tempN = n;
            long count = 1;
            while (m  >= (tempN << 1)){
                res += (count <<= 1);
                tempN <<= 1;
                m -= tempN;
            }
        }
    }
}
